package com.dylon.sort;

import java.util.Arrays;

/**
 * 计数排序
 */
public class CountingSort {

    public static void main(String[] args) {
        int[] a = new int[]{1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
        System.out.println(Arrays.toString(a));
        countSort(a);
        System.out.println(Arrays.toString(a));
    }


    public static void countSort(int[] a) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i=0; i<a.length; i++) { // 找到max和min
            if (a[i]<min)
                min=a[i];
            if (a[i]>max)
                max=a[i];
        }
        int[] count = new int[max-min+1]; // 对元素进行计数
        for (int i=0; i<a.length; i++) {
            count[a[i]-min]++;
        }
        //排序取值
        int index = 0;
        for (int i=0; i<count.length; i++) {
            while (count[i]-- > 0) {
                a[index++] = i+min; // 有min才是真正值
            }
        }
    }

    /*
    计数排序是一种特殊的桶排序，每个桶的大小为1，每个桶不在用List表示，而通常用一个值用来计数。

    在「设计具体算法的时候」，先找到最小值min，再找最大值max。
    然后创建这个区间大小的数组,从min的位置开始计数，这样就可以最大程度的压缩空间，提高空间的使用效率。

     */

}
